package unionfindset.impl;

import java.util.Arrays;

import unionfindset.proto.UnionFindSet;

/**
 * @author wujun
 * @date 17-11-29.
 *
 * 粗糙的实现
 */
public class RawUnionFindSet implements UnionFindSet<Integer> {
    int[] set;
    int count;

    @Override
    public void init(int n) {
        set = new int[n + 1];
        count = n;

        for (int i = 0; i < set.length; i++) {
            set[i] = i;
        }
    }

    @Override
    public void union(Integer p, Integer q) {
        int parentP = find(p);
        int parentQ = find(q);

        if (parentP == parentQ) {
            return;
        }

        set[parentP] = parentQ;
        set[p] = parentQ;
    }

    @Override
    public Integer find(Integer p) {
        int parent = set[p];
        while (parent != p) {
            p = parent;
            parent = set[p];
        }

        set[p] = parent;
        return parent;
    }

    @Override
    public boolean connected(Integer p, Integer q) {
        int parentP = find(p);
        int parentQ = find(q);

        return parentP == parentQ;
    }

    @Override
    public void display() {
        System.out.println(Arrays.toString(set));
    }
}
